package 动态数组.队列;

import 动态数组.队列.接口.AbstractArrayDoubleEndStack;

import java.util.Iterator;

public class ArrayDoubleEndStack<E> extends AbstractArrayDoubleEndStack<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private E[] data;
    //双端栈的左指针
    private int ltop;
    //双端栈的右指针
    private int rtop;

    public ArrayDoubleEndStack(){
        data = (E[]) new Object[DEFAULT_CAPACITY];
        ltop = -1;
        rtop = data.length;
    }

    @Override
    public int size() {
        return leftSize() + rightSize();
    }

    public int leftSize(){
        return ltop + 1;
    }

    public int rightSize(){
        return data.length - rtop;
    }

    @Override
    public boolean isEmpty() {
        return leftIsEmpty() && rightIsEmpty();
    }

    public boolean leftIsEmpty(){
        return ltop == -1;
    }

    public boolean rightIsEmpty(){
        return rtop == data.length;
    }

    public void leftPush(E element){
        //扩容问题
        if (ltop + 1 == rtop){
            //扩容两倍
            resize(data.length * 2);
        }
        //添加元素
        data[++ltop] = element;
    }

    
    public void rightPush(E element){
        //扩容问题
        if (rtop - 1 == ltop){
            //扩容两倍
            resize(data.length * 2);
        }
        //添加元素
        data[--rtop] = element;
    }

    private void resize(int newLength) {
        E[] ret = (E[]) new Object[newLength];
        for (int i = 0; i <= ltop; i++) {
            ret[i] = data[i];
        }
        int index = rtop;
        for (int i = newLength - rightSize(); i < newLength; i++) {
            ret[i] = data[index++];
        }
        rtop = newLength - rightSize();
        data = ret;
    }

    public int getCapacity(){
        return data.length;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("leftSize:%d,rightSize:%d,capacity:%d",leftSize(),rightSize(),getCapacity()));
        if (isEmpty()){
            return sb.append("[[],[]]").toString();
        }
        if (leftIsEmpty()){
            sb.append("[[],");
        }else {
            sb.append("[[");
            for (int i = 0; i <= ltop; i++) {
                sb.append(data[i]);
                if (i == ltop){
                    sb.append(']');
                    sb.append(',');
                }else {
                    sb.append(",");
                }
            }
        }
        if (rightIsEmpty()){
            sb.append("[]]");
        }else {
            sb.append('[');
            for (int i = rtop; i < data.length; i++) {
                sb.append(data[i]);
                if (i == data.length - 1){
                    sb.append("]]");
                }else {
                    sb.append(',');
                }
            }
        }

        return sb.toString();
    }

    public E leftPop(){
        //弹出元素
        if (leftIsEmpty()){
            throw new IllegalArgumentException("left Stack is null so it can not be Pop");
        }
        E ret = data[ltop--];
        //缩容问题
        if (size() == data.length / 4 && getCapacity() > DEFAULT_CAPACITY){
            resize(data.length / 2);
        }
        return ret;

    }

    public E rightPop(){
        //弹出元素
        if (rightIsEmpty()){
            throw new IllegalArgumentException("right Stack is null so it can not be Pop");
        }
        E ret = data[rtop++];
        //缩容问题
        if (size() == data.length / 4 && getCapacity() > DEFAULT_CAPACITY){
            resize(data.length / 2);
        }
        return ret;
    }

    public E leftPeek(){
        if (leftIsEmpty()){
            return  null;
        }
        return data[ltop];
    }

    public E rightPeek(){
        if (rightIsEmpty()){
            return  null;
        }
        return data[rtop];
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null){
            return false;
        }
        if (this == obj){
            return true;
        }
        if (getClass() != obj.getClass()){
            return false;
        }
        ArrayDoubleEndStack other = (ArrayDoubleEndStack) obj;
        if (size() == other.size() && leftSize() == other.leftSize() && rightSize() == other.rightSize()){
            //当前（本类）双端栈的指针
            int l1 = 0;
            //传入双端栈的指针
            int l2 = 0;
            while (l1 <= ltop){
                if (!data[l1].equals(other.data[l2])){
                    return false;
                }
                l1++;
                l2++;
            }
            l1 = rtop;
            l2 = other.rtop;
            while (l1 < data.length){
                if (!data[l1].equals(other.data[l2])){
                    return false;
                }
                l1++;
                l2++;
            }
            return true;
        }
        return false;
    }

    @Override
    public void clear() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
        ltop = -1;
        rtop = data.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayDoubleEndStackIterator();
    }

    class ArrayDoubleEndStackIterator implements Iterator<E> {
        int cur = 0;

        @Override
        public boolean hasNext() {
            if (cur < ltop + 1){
                return true;
            }else if (cur == ltop + 1){
                cur = rtop;
            }
            if (cur < data.length){
                return true;
            }
            return false;
        }

        @Override
        public E next() {
            return data[cur++];
        }
    }
}
